package experiment2.lcsubsequence;

import java.util.Random;
import java.util.Scanner;

public class LCSuSequence {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Random random = new Random();
        String tempString = "abcdefghigklmnopqrstuvwxyz";

        System.out.println("请分别输入两个字符串的个数:");
        while (true) {
            int n1 = scanner.nextInt();
            int n2 = scanner.nextInt();
            StringBuilder s1 = new StringBuilder();
            StringBuilder s2 = new StringBuilder();

            for (int i = 0; i < n1; i++) {
                s1.append(tempString.charAt(random.nextInt(26)));
            }
            for (int i = 0; i < n2; i++) {
                s2.append(tempString.charAt(random.nextInt(26)));
            }
            System.out.println(s1.toString());
            System.out.println(s2.toString());
            subsequence(s1.toString(), s2.toString());
        }
    }

    public static void subsequence(String s1, String s2) {
        int length1 = s1.length();
        int length2 = s2.length();
        int[][] array = new int[length1 + 1][length2 + 1];
        int[][] track = new int[length1 + 1][length2 + 1];
        for (int i = 1; i <= length1; i++) {
            for (int j = 1; j <= length2; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    array[i][j] = array[i - 1][j - 1] + 1;
                    track[i][j] = 1;
                } else if (array[i - 1][j] > array[i][j - 1]) {
                    array[i][j] = array[i - 1][j];
                    track[i][j] = 2;
                } else {
                    array[i][j] = array[i][j - 1];
                    track[i][j] = 3;
                }
            }
        }


        String s = "";

        int i = length1;
        int j = length2;
        while (i > 0 && j > 0) {
            if (track[i][j] == 1) {
                s = (s1.charAt(i - 1)) + s;
                i--;
                j--;
            } else if (track[i][j] == 2) {
                i--;
            } else {
                j--;
            }
        }
        System.out.println("最长公共子序列有" + array[length1][length2] + "个字符,序列为" + s);
    }
}
